Error diffusion is a well known technique for reducing continuous tone images to a pattern of black and white spots for printing on a binary device. A process for error diffusion is disclosed in an article entitled "An Adaptive Algorithm for Spatial Greyscale" by Robert W. Floyd and Louis Steinberg, Proc. Soc. lnf. Disp. 17, 75-77 (1976). The process involves an algorithm which determines whether or not to print a dot at a certain location based on a comparison of the continuous tone data with a threshold value. Gray levels above a chosen threshold are assigned a dot to be printed and those below the threshold are not assigned a dot to be printed. If the threshold corresponds to midway between black and white, the method always chooses the closer of black and white. The inherent error resulting from such a choice is propagated in specified amounts to adjacent picture elements or pixels not yet considered to change the pixels prior to thresholding. This method produces a more accurate representation of a gray tone over a small area encompassing several dots than conventional halftoning. Hence, the error in the intensity of the digital image is diffused and, on average, zero.
The fraction of the error added to each neighbor depends on a set of weights, the total error being multiplied by the weight corresponding to a given neighbor and then added to the value of that neighbor. The choice of weight can greatly affect the image quality, and much has been said about weights appropriate for giving pleasing results. Examples of weights other than those in the original Floyd and Steinberg algorithm may be found in papers by Jarvis, Judice, and Ninke ("A Survey of Techniques for Display of Continuous-Tone Pictures on Bilevel Displays", Computer Graphics and Image Processing, 5, pp. 13-40, 1976), Stucki, ("Image Processing for Document Reproduction", Advances in Diaital Imaae Processina, pp. 177-218, New York, Plenum, 1979), and Fan, ("A Simple Modification of Error Diffusion Weights", Proceedings of the IS&T 46th Annual Conference, pp. 113-114, Boston 1993) and in U.S. Pat. No. 5,353,127 to Shiau et al.
In the case of color, however, one cannot just apply simple error diffusion to each color component independently. To do so would produce noisy images. For example, a light blue can be produced by magenta and cyan pixels. But if the magenta and cyan are processed independently, then some pixels may have both magenta and cyan, yielding blue, while others have no ink at all, giving white. This mixture of white, blue, magenta and cyan will have more contrast and look noisier than pixels of magenta and cyan alone. The process of independently processing each channel can result in any and all of the eight possible pixel colors distributed over an image area.
The problem of image noisiness can be reduced by the method of vector error diffusion. In this scheme the color chosen for each pixel is the color in a selected color space closest to the desired value, where the desired value is the input value modified by the errors diffused from neighboring pixels. This tends to confine the pixel colors to a subset near the input value and reduces the noise. What is known as vector error diffusion was described in a paper by Venable et al., "Selection and Use of Small Color Sets for Pictorial Display", Proc IS&T Annual Meeting, Rochester, 1990 and in a paper by Miller et al. "Color Halftoning Using Error Diffusion and a Human Visual System Model", Proc IS&T Annual Meeting, Rochester, 1990. In vector error lo diffusion colors are treated as points in a three dimensional space, with the colors printable or displayable at a given pixel discrete locations within that space. When a continuous tone color is to be displayed, the closest displayable or printable color is selected, and the error (the difference between the input color and added error, and the output color) is calculated as a vector in color space. Here, the "closeness" might be the simple distance in color space or a weighted distance based on the human visual model. The vector is the difference between the desired color and the available color. The (vector) error is then diffused in the same way as in normal error diffusion.
There are, however, some problems with vector error diffusion. One is the difficult three dimensional computation required to find the closest color at each pixel. Second, the method is unstable for colors that are near the gamut boundary. With these colors the addition of errors from neighboring pixels can take the desired color out of the gamut. Then the nearest color will generate an error that leads even further outside the gamut and the method collapses or produces unstable results. A third problem is that the method may still not select the optimal set of colors. For example, it may produce a gray from white and black pixels, where a smoother image might be produced if cyan, magenta and yellow were used because there would be less luminance contrast.
A solution to this third problem was proposed by U.S. Pat. No. 5,621,546 to Klassen et al. That patent suggests performing the error diffusion in two steps. The first is a simple error diffusion performed on the sum of the requested colorant amounts for the color separations. This indicates when color is needed, but does not tell which color should be selected. The pixel color closest to the desired color is chosen using a vector error diffusion process. This tends to disperse the color giving broad coverage of light colors rather than a pattern of dark spots on a white background. The improved image quality is at a cost of increased complexity (namely an additional error diffusion calculation).
The references cited herein are incorporated by reference for their teachings.